// let quickSort = require("./quickSort.js")
// 桶排序
const bucketSort = (array, bucketSize) => {
  if (array.length === 0) {
    return array;
  }

  let i = 0;
  let minValue = array[0];
  let maxValue = array[0];
  for (i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i]; //输入数据的最小值
    } else if (array[i] > maxValue) {
      maxValue = array[i]; //输入数据的最大值
    }
  }

  //桶的初始化
  const DEFAULT_BUCKET_SIZE = 5; //设置桶的默认数量为 5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  //利用映射函数将数据分配到各个桶中
  for (i = 0; i < array.length; i++) {
    buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
  }
  array.length = 0;
  for (i = 0; i < buckets.length; i++) {
    // 由于快排没有改变原来得数组 所以此次定义一个变量
     let a =  quickSort(buckets[i]); //对每个桶进行排序，这里使用了快速排序
   //   buckets[i].sort((a,b)=>a-b)
    for (let j = 0; j <a.length; j++) {
      array.push(a[j]);
    }
  }
  return array;
};

let a = [2, 1, 4, 3, 5, 19, 12]
console.log(bucketSort(a))

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  const flag = arr[0]
  const left = []
  const right = []
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < flag) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  const temp  = [...quickSort(left), flag, ...quickSort(right)]
  return temp
}